package com.xinpan.exercise;

	import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Stack<Character> ps = new Stack<Character>();
        for(int i = 0; i < s.length(); i++)
        {
            char v = s.charAt(i);
            if(v == '(' || v == '[' || v == '{')
                ps.push(v);
            else
            {
                if(ps.size() == 0)
                    return false;
                else if(v == ')' && ps.peek() != '(')
                    return false;
                else if(v == ']' && ps.peek() != '[')
                    return false;
                if(v == '}' && ps.peek() != '{')
                    return false;
                
                ps.pop();
            }
        }
        if(ps.size() > 0)
            return false;
            
        return true;
    }
}
